
//dynamic programming

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

FILE *fp;

int C;     // capacity of the knapsack (total weight that can be stored)
int N;    // number of items available
int *w;  // vector of item weights
int *v;  // vector of item profits or values
int *kindex;  // a list of indexes (we can sort these instead of moving the items)
int QUIET=0; // this can be set to 1 to suppress output

// function prototypes
extern void read_knapsack_instance(char *filename);
int DP(int *v,int *wv, int n, int W, int *x);
extern int print_sol2(int *s,  int *tv, int *tw);

int main(int argc, char *argv[1])
{
  int *x;    // binary vector indicating items to pack
  int tv, tw;  // total value and total weight of items packed

  read_knapsack_instance(argv[1]);

  if((x = (int *)malloc((N+1)*sizeof(int)))==NULL)
  {
    fprintf(stderr,"Problem allocating table for DP\n");
    exit(1);
  }

  DP(v,w,N,C,x);
  print_sol2(x,&tw,&tv);
  return(0);
}

int DP(int *v,int *wv, int n, int W, int *x)
{
  // the dynamic programming function for the knapsack problem
  // the code was adapted from p17 of http://www.es.ele.tue.nl/education/5MC10/solutions/knapsack.pdf

  // v array holds the values / profits / benefits of the items
  // wv array holds the sizes / weights of the items
  // n is the total number of items
  // W is the constraint (the weight capacity of the knapsack)
  // x is the binary solution vector, a 1 in position n means pack item number n+1. A zero means do not pack it.

  int **V, **keep;  // 2d arrays for use in the dynamic programming solution
  // keep[][] and V[][] are both of size (n+1)*(W+1)

  int i, w, K;

  // Dynamically allocate memory for variables V and keep
  /* ADD CODE HERE */
  V = (int **)malloc((n+1)*sizeof(int*));
  for(int i = 0; i<n+1; i++){
      V[i] = (int *)malloc((W+1)*sizeof(int));
  }
  keep = (int **)malloc((n+1)*sizeof(int*));
  for(int i = 0; i<W+1; i++){
      keep[i] = (int *)malloc((W+1)*sizeof(int));
  }

 //  set the values of the zeroth row of the partial solutions table to zero
  /* ADD CODE HERE */
  for(w=0; w<=W; w++){
      V[0][w] = 0;
  }

 // main dynamic programming loops , adding one item at a time and looping through weights
  /* ADD CODE HERE */
  for(i=1; i<=n; i++){
    for(w=0; w<=W; w++){
      if((wv[i] <= w)&&(v[i]+V[i-1][w-wv[i]] > V[i-1][w])){
	  V[i][w] = v[i]+V[i-1][w-wv[i]];
	  keep[i][w] = 1;
      }
      else{
	  V[i][w] = V[i-1][w];
	  keep[i][w] = 0;
      }
    }
  }

  // now discover which items were in the optimal solution
  /* ADD CODE HERE */
  K = W;
  printf("items in the optimal solution are\n");
  for(i=n; i>0; i--){
    if(keep[i][K] == 1){
       printf("%d\n", i);
       x[i] = 1;
       K = K - wv[i];
    }
  }
  return V[n][W];
}


